package leetcode_800;

/**
 *@author 周杨
 *NumberOfMatchingSubsequences_792 给定一个字符串 再给定一个字符串数组 问数组里有多少字符串是其子串
 *describe:匹配即可 优化可以用两个Map记录 contains算法去重 AC 12%
 *2018年10月23日 上午9:34:44
 */
public class NumberOfMatchingSubsequences_792 {
	/**
	 * describe:暴力解 每个都匹配一次 AC 12%
	 * 2018年10月23日 上午9:33:51
	 */
	public int numMatchingSubseq1(String S, String[] words) {
        int res=0;
        for(String word:words) {
        	if(isSubsequence(word, S))
        		++res;
        }
        return res;
    }
	
	public boolean isSubsequence(String a, String b){
        int i=0, j=0;
        while(i<a.length() && j<b.length()) if (a.charAt(i)==b.charAt(j++)) i++;
        return i==a.length();
	}
}
